module Maze
  module Algorithm
    class RecursiveBacktracker

      attr_reader :maze
      
      def initialize(maze)
        @maze = maze
      end

      # Start from any random point in the grid.
      def run
        find_path_from(Point.random(maze))
      end

      # 1. From the current point pick a neighbouring point which has not been
      #    visited in any direction.
      # 2. The coordinates of the next point has to be fetched w.r.t the
      #    direction of traversal. In certain cases like for edge points its
      #    possible to step out of bounds. We ignore these moves and pick
      #    another one which will keep us within the grid.
      # 3. When there is a valid move to a neighbouring point and it has not been
      #    visited earlier, both points are connected. Now the neighbouring point
      #    becomes the current point.
      # 4. We continue recursively connecting paths until we reach certain points
      #    from which there are no unvisited neighbours, in which case we
      #    continuously backtrack until we find a neighbouring unvisited point.
      # 5. The algorithm ends its run when it returns to initial point from where
      #    it started it's traversal. At this point it's guaranteed to have
      #     visited all the other points.
      def find_path_from(current_point)
        maze.random_directions.each do |direction|
          next_point = current_point.next(maze, direction)

          if next_point && next_point.unvisited?(maze)
            maze.connect(current_point, next_point, direction)

            find_path_from(next_point)
          end
        end
      end

    end
  end
end

